class Solution {
    public String reverseWords(String s) {
        // 1.去除首尾以及中间多余空格
        char[] arr = s.toCharArray();
        arr = removeSpace(arr);
        // 2.反转整个字符串
        reverseString(arr, 0, arr.length - 1);
        // 3.反转各个单词
        reverseEachWord(arr);
        return new String(arr);    
    }

    //用 快慢指针 去除首尾以及中间多余空格，可参考数组元素移除的题解
    private char[] removeSpace(char[] arr) {
        int slow = 0;
        for(int fast = 0; fast < arr.length; fast++){
            if(arr[fast] != ' '){   //遇到非空格就处理，即删除所有空格。
                if(slow != 0)     //手动控制空格，给单词之间添加空格 slow != 0说明不是第一个单词，需要单词前添加空格
                    arr[slow++] = ' '; 
                while(fast < arr.length && arr[fast] != ' ')
                    arr[slow++] = arr[fast++];
            }
        }
        //这里需要注意的是，最后需要重新获取我们需要的部分，只要0-slow部分
        char[] newChars = new char[slow];
        System.arraycopy(arr, 0, newChars, 0, slow);
        return newChars;
    }

    //双指针实现指定范围内字符串反转
    public void reverseString(char[] arr, int start, int end) {
        while (start < end) {
            char tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
            start++;
            end--;
        }
    }

    //单词反转
    private void reverseEachWord(char[] arr) {
        int start = 0;
        //end <= s.length() 这里的 = ，是为了让 end 永远指向单词末尾后一个位置，这样 reverse 的实参更好设置
        for (int end = 0; end <= arr.length; end++) {
            // end 每次到单词末尾后的空格或串尾,开始反转单词
            if (end == arr.length || arr[end] == ' ') {
                reverseString(arr, start, end - 1);
                start = end + 1;
            }
        }
    }

}
